package com.fyt.algorithm.Leecode.day2;

import java.util.Arrays;

public class FindTheMedianofTwoPositiveOrdinalArrays {

    /**
     * 暴力的方案
     * @param nums1
     * @param nums2
     * @return
     */
   /* public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
     int nums3length=    nums1.length+nums2.length;
     int [] nums3=new int[nums3length];
        int index=0;
        double res=0;

        for (int i = 0; i <nums1.length ; i++) {
            nums3[index++]=nums1[i];
        }

        for (int i = 0; i <nums2.length ; i++) {
            nums3[index++]=nums2[i];
        }

        Arrays.sort(nums3);

        System.out.println(Arrays.toString(nums3));

        if(nums3length%2==0){
            res=(nums3[nums3length/2]+nums3[nums3length/2-1])*1.0/2;
        }
        else {
            res=nums3[nums3length/2]*1.0;


        }
       return  res;
    }
*/
    /**
     * 归并排序的思想,双指针的方案
     * @param args
     */

 /*   public static double findMedianSortedArrays(int[] nums1, int[] nums2){
        int nums3length=    nums1.length+nums2.length;
        int [] nums3=new int[nums3length];
        double res=0;
        int pointer1=0;
        int pointer2=0;
        int index=0;
        while (pointer1<nums1.length&&pointer2<nums2.length){
            if(nums1[pointer1]<nums2[pointer2]){
                nums3[index++]=nums1[pointer1++];
            }
            else {
                nums3[index++]=nums2[pointer2++];
            }

        }
        while (pointer1<nums1.length){
            nums3[index++]=nums1[pointer1++];
        }
        while (pointer2<nums2.length){
            nums3[index++]=nums2[pointer2++];
        }


        System.out.println(Arrays.toString(nums3));

        if(nums3length%2==0){
            res=(nums3[nums3length/2]+nums3[nums3length/2-1])*1.0/2;
        }
        else {
            res=nums3[nums3length/2]*1.0;


        }

        return res;
    }*/


    /**
     * 划分数组+二分查找
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2){
      if(nums2.length<nums1.length){
         return findMedianSortedArrays(nums2,nums1);
      }
      int n=nums1.length;
      int m=nums2.length;

      int left=0,right=n;
      int median1=0, median2=0;
      while (left<=right){
          int i=(left+right)/2;
          int j=(m+n+1)/2-i;
          int nums_il1=(i==0?Integer.MIN_VALUE:nums1[i-1]);
          int nums_jl1=(j==0?Integer.MIN_VALUE:nums2[j-1]);
          int nums_i=(i==n? Integer.MAX_VALUE:nums1[i]);
          int nums_j=(j==m? Integer.MAX_VALUE:nums2[j]);

          if (nums_il1<=nums_j){
              median1=Math.max(nums_il1,nums_jl1);
              median2=Math.min(nums_i,nums_j);
              left=i+1;

          }
          else {
              right=i-1;                      //为什么这里不对median重新赋值
          }


      }




        return (n+m)%2==0?(median1+median2)/2.0:median1;
    }


    public static void main(String[] args) {
        int [] nums1={1,3};
        int [] nums2={2};
        System.out.println(  findMedianSortedArrays(nums1,nums2));


    }
}
